Задача #M112B

Мухаммадамин очень увлекается рисованием узоров. Это увлечение появилось у него с раннего детства, когда он только начал держать ручку в руках — тогда он нарисовал "красивые" "узоры" на всех стенах дома.

Сейчас он уже взрослый. Поэтому теперь он рисует узоры не на стенах, а на миллиметровке.

В узоре размером \(N \times M\), состоящем только из чёрных и белых клеток, если ни в одной строке и ни в одном столбце не встречается подряд 3 одинаковых по цвету клетки, то Мухаммадамин считает узор красивым, а степень красоты такого узора равна количеству чёрных клеток в нём.

В данный момент у Мухаммадамина есть миллиметровка размером \(A \times B\). Мухаммадамин хочет нарисовать на ней узор. Помогите ему определить, какова максимально возможная степень красоты узора, который он сможет нарисовать на этой бумаге.

В первой строке входного файла дано одно целое число \(T(1 \le T \le 10^5)\) — количество тестов.

В каждой из следующих \(T\) строк даны по два целых числа \(A(1 \le A \le 10^9)\) и \(B(1 \le B \le 10^9)\).

Для каждого теста в отдельной строке выведите одно целое число — максимальную степень красоты узора размера \(A \times B\).